d3-voronoi

What is d3-voronoi?

The d3-voronoi npm package is a part of the D3.js library and is used to compute Voronoi diagrams. Voronoi diagrams partition a plane into regions based on the distance to a specific set of points. This package is useful for spatial analysis, data visualization, and creating interactive graphics.

What are d3-voronoi's main functionalities?

Compute Voronoi Diagram

This feature allows you to compute a Voronoi diagram for a given set of points. The code sample demonstrates how to create a Voronoi diagram for three points within a specified extent.

const d3 = require('d3-voronoi');
const points = [[200, 200], [400, 400], [600, 600]];
const voronoi = d3.voronoi().extent([[0, 0], [800, 800]]);
const diagram = voronoi(points);
console.log(diagram.cells);

Find Voronoi Cell for a Point

This feature allows you to find the Voronoi cell that contains a specific point. The code sample demonstrates how to find the cell for the point (300, 300).

const d3 = require('d3-voronoi');
const points = [[200, 200], [400, 400], [600, 600]];
const voronoi = d3.voronoi().extent([[0, 0], [800, 800]]);
const diagram = voronoi(points);
const cell = diagram.find(300, 300);
console.log(cell);

Render Voronoi Diagram with SVG

This feature allows you to render a Voronoi diagram using SVG. The code sample demonstrates how to create an SVG representation of the Voronoi diagram for three points.

const d3 = require('d3-voronoi');
const points = [[200, 200], [400, 400], [600, 600]];
const voronoi = d3.voronoi().extent([[0, 0], [800, 800]]);
const diagram = voronoi(points);
const svg = `<svg width="800" height="800">
  ${diagram.cells.map(cell => `<path d="M${cell.halfedges.map(i => diagram.edges[i].join('L')).join('L')}Z" stroke="black" fill="none" />`).join('')}
</svg>`;
console.log(svg);

Other packages similar to d3-voronoi

d3-delaunay

The d3-delaunay package is used to compute Delaunay triangulations, which are closely related to Voronoi diagrams. Delaunay triangulations can be used to derive Voronoi diagrams, and they are often used in similar spatial analysis and data visualization tasks. Compared to d3-voronoi, d3-delaunay provides more robust and efficient algorithms for computing these structures.

voronoi-diagram

The voronoi-diagram package is a lightweight library for computing Voronoi diagrams. It is less feature-rich compared to d3-voronoi but can be a good choice for simple use cases where you need to compute Voronoi diagrams without the additional overhead of the D3.js library.

README

d3-voronoi

Deprecation notice: Consider using the newer d3-delaunay instead of d3-voronoi. Based on Delaunator, d3-delaunay is 5-10× faster than d3-voronoi to construct the Delaunay triangulation or the Voronoi diagram, is more robust numerically, has Canvas rendering built-in, allows traversal of the Delaunay graph, and a variety of other improvements.

---

This module implements Steven J. Fortune’s algorithm for computing the Voronoi diagram or Delaunay triangulation of a set of two-dimensional points. This implementation is largely based on work by Raymond Hill.

Voronoi diagrams are not only visually attractive but practical tools for interaction, such as to increase the target area of points in a scatterplot. See “Strikeouts on the Rise” in The New York Times and this multi-line chart for examples; also see Tovi Grossman’s paper on bubble cursors for a related technique. Voronoi diagrams can also be used to automate label positioning, and Delaunay meshes are useful in computing adjacency or grouping of visual elements.

Installing

If you use NPM, npm install d3-voronoi. Otherwise, download the latest release. You can also load directly from d3js.org, either as a standalone library or as part of D3 4.0. AMD, CommonJS, and vanilla environments are supported. In vanilla, a d3 global is exported:

<script src="https://d3js.org/d3-voronoi.v1.min.js"></script>
<script>

var voronoi = d3.voronoi();

</script>

Try d3-voronoi in your browser.

API Reference

# d3.voronoi() <>

Creates a new Voronoi layout with default x- and y- accessors and a null extent.

# voronoi(data) <>

Computes the Voronoi diagram for the specified data points.

# voronoi.x([x]) <>

If x is specified, sets the x-coordinate accessor. If x is not specified, returns the current x-coordinate accessor, which defaults to:

function x(d) {
  return d[0];
}

# voronoi.y([y]) <>

If y is specified, sets the y-coordinate accessor. If y is not specified, returns the current y-coordinate accessor, which defaults to:

function y(d) {
  return d[1];
}

# voronoi.extent([extent]) <>

If extent is specified, sets the clip extent of the Voronoi layout to the specified bounds and returns the layout. The extent bounds are specified as an array [[x0, y0], [x1, y1]], where x0 is the left side of the extent, y0 is the top, x1 is the right and y1 is the bottom. If extent is not specified, returns the current clip extent which defaults to null. A clip extent is required when using voronoi.polygons.

# voronoi.size([size]) <>

An alias for voronoi.extent where the minimum x and y of the extent are ⟨0,0⟩. Equivalent to:

voronoi.extent([[0, 0], size]);

# voronoi.polygons(data) <>

Returns a sparse array of polygons, one for each unique input point in the specified data points, corresponding to the cells in the computed Voronoi diagram. Equivalent to:

voronoi(data).polygons();

See diagram.polygons for more detail. Note: an extent is required.

# voronoi.triangles(data) <>

Returns the Delaunay triangulation of the specified data array as an array of triangles. Each triangle is a three-element array of elements from data. Equivalent to:

voronoi(data).triangles();

See diagram.triangles for more detail.

# voronoi.links(data) <>

Returns the Delaunay triangulation of the specified data array as an array of links. Each link has source and target attributes referring to elements in data. Equivalent to:

voronoi(data).links();

See diagram.links for more detail.

Voronoi Diagrams

# diagram <>

The computed Voronoi diagram returned by voronoi has the following properties:

• edges - an array of edges.
• cells - a sparse array of cells, one for each unique input point.

For each set of coincident input points, one of the points is chosen arbitrarily and assigned the associated cell; the other coincident input points’ entries are missing from the returned sparse array.

# diagram.polygons() <>

Returns a sparse array of polygons clipped to the extent, one for each cell (each unique input point) in the diagram. Each polygon is represented as an array of points [x, y] where x and y are the point coordinates, and a data field that refers to the corresponding element in data. Polygons are open: they do not contain a closing point that duplicates the first point; a triangle, for example, is an array of three points. Polygons are also counterclockwise, assuming the origin ⟨0,0⟩ is in the top-left corner.

For each set of coincident input points, one of the points is chosen arbitrarily and assigned the associated polygon; the other coincident input points’ entries are missing from the returned sparse array.

# diagram.triangles() <>

Returns the Delaunay triangulation of the specified data array as an array of triangles. Each triangle is a three-element array of elements from data. Since the triangulation is computed as the dual of the Voronoi diagram, and the Voronoi diagram is clipped by the extent, a subset of the Delaunay triangulation is returned.

# diagram.links() <>

Returns the Delaunay triangulation of the specified data array as an array of links, one for each edge in the mesh. Each link has the following attributes:

• source - the source node, an element in data.
• target - the target node, an element in data.

Since the triangulation is computed as the dual of the Voronoi diagram, and the Voronoi diagram is clipped by the extent, a subset of the Delaunay links is returned.

# diagram.find(x, y[, radius]) <>

Returns the nearest site to point [x, y]. If radius is specified, only sites within radius distance are considered.

See Philippe Rivière’s bl.ocks.org/1b7ddbcd71454d685d1259781968aefc for an example.

# cell

Each cell in the diagram is an object with the following properties:

• site - the site of the cell’s associated input point.
• halfedges - an array of indexes into diagram.edges representing the cell’s polygon.

# site

Each site in the diagram is an array [x, y] with two additional properties:

• index - the site’s index, corresponding to the associated input point.
• data - the input data corresponding to this site.

# edge

Each edge in the diagram is an array [[x0, y0], [x1, y1]] with two additional properties:

• left - the site on the left side of the edge.
• right - the site on the right side of the edge; null for a clipped border edge.